package features.advance.leetcode.geometry.doublepointer.easy;

/**
 * 234. 回文链表
 *
 * 难度  简单
 * 请判断一个链表是否为回文链表。
 *
 * 示例 1:
 *
 * 输入: 1->2
 * 输出: false
 * 示例 2:
 *
 * 输入: 1->2->2->1
 * 输出: true
 * 进阶：
 * 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 *
 */

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution234 {

    public boolean isPalindrome(ListNode head) {


        return true;
    }

    public static void main(String[] args) {

        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(0);
        ListNode listNode4 = new ListNode(2);
        ListNode listNode5 = new ListNode(1);
//        ListNode listNode6 = new ListNode(2);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        boolean palindrome = new Solution234() {
            @Override
            public boolean isPalindrome(ListNode head) {
                if (head == null) {
                    return true;
                }

                // 找到前半部分链表的尾节点并反转后半部分链表
                ListNode firstHalfEnd = endOfFirstHalf(head);
                ListNode secondHalfStart = reverseList(firstHalfEnd.next);

                // 判断是否回文
                ListNode p1 = head;
                ListNode p2 = secondHalfStart;
                boolean result = true;
                while (result && p2 != null) {
                    if (p1.val != p2.val) {
                        result = false;
                    }
                    p1 = p1.next;
                    p2 = p2.next;
                }

                // 还原链表并返回结果
                firstHalfEnd.next = reverseList(secondHalfStart);
                return result;
            }

            private ListNode reverseList(ListNode head) {
                ListNode prev = null;
                ListNode curr = head;
                while (curr != null) {
                    ListNode nextTemp = curr.next;
                    curr.next = prev;
                    prev = curr;
                    curr = nextTemp;
                }
                return prev;
            }

            private ListNode endOfFirstHalf(ListNode head) {
                ListNode fast = head;
                ListNode slow = head;
                while (fast.next != null && fast.next.next != null) {
                    fast = fast.next.next;
                    slow = slow.next;
                }
                return slow;
            }
        }.isPalindrome(listNode1);
        System.out.println(palindrome);

    }


}
